package org.raymond.iworks.study.basic.structure.tree.avl;

/**
 * 二叉排序树可能存在的问题
 * 数列{1,2,3,4,5,6}
 * 1
 *  2
 *   3
 *    4
 *     5
 *      6
 * 1) 左子树全部为空,从形式上看,更像一个单链表
 * 2) 插入速度没有影响
 * 3) 查询速度明显降低(因为需要依次比较),不能发挥BST的优势,
 * 因为每次还需要比较左子树,其查询速度比单链表更慢
 * 4) 解决方案-平衡二叉树(AVL)
 * 基本介绍
 * 1) 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree),
 * 又被称为AVL树,可以保证查询效率较高
 * 2) 具有以下特点: 它是一颗空树或它的左右两个子树的高度差的绝对值不超过1,并且
 * 左右两个子树都是一颗平衡二叉树.平衡二叉树的常用实现方法有红黑树,AVL,替罪羊树,
 * Treap,伸展树等
 * 应用案例-单旋转(左旋转)
 * 数列:{4,3,6,5,7,8}
 * 二叉排序树:
 *   4
 * 3   6
 *    5  7
 *        8
 * rightHigh(3)-leftHigh(1)>1,不是AVL树
 * 怎么处理->左旋转
 * 1, 创建一个新的节点,值为当前根节点的值(4)
 * 2, 把新节点的左子树设置为当前节点的左子树
 * newNode.left=curNode.left
 * 3, 把新节点的右子树设置为当前节点的右子树的左子树
 * newNode.right=curNode.right.left
 * 4, 把当前节点的值换成右子节点的值
 * curNode.value=curNode.right.value
 * 5,把当前节点的右子树设置成右子树的右子树
 * curNode.right=curNode.right.right
 * 6,把当前节点的左子树设置为新节点
 * curNode.left=newNode
 * 结果如下:
 *     6
 *  4
 * 3  5  6(Removed)
 *        7
 *         8
 *
 * 应用案例-单旋转(右旋转)
 * 数列:{10,12,8,9,7,6}
 * 二叉排序树:
 *     10
 *   8   12
 *  7 9
 * 6
 * leftHeight()-rightHeight()>1,不是AVL树
 * 怎么处理->右旋转(降低左子树高度),以root节点为当前节点进行处理
 * 1,创建新节点,节点值为当前节点的值(10)
 * newNode.value=this.value=10
 * 2,将当前节点的右子树挂在新节点的右侧
 * newNode.right=this.right
 * 3,将当前节点的左子树的右子树挂在新节点的左侧
 * newNode.left=this.left.right
 * 4,将上升节点(当前节点的左节点)的值覆盖当前节点的值
 * this.value=this.left.value
 * 5,将上升节点的左子树挂到当前节点下,原上升节点将被废弃
 * this.left=this.left.left
 * 6,将新节点挂到当前节点的右子树上
 * this.right=newNode
 * 结果如下:
 *     8
 *   8(Removed)
 *  7      10
 * 6      9  12
 *
 * 应用案例-双旋转
 * 数列:{10,11,7,6,8,9}
 * 二叉排序树:
 *     10
 *  7    11
 * 6 8
 *    9
 * 符合右旋转的条件:leftHeight(3)-rightHeight(1)>1
 * 右旋转的结果:
 *   7
 * 6    10
 *    8    11
 *     9
 * 问题分析:
 * 当符合右旋转的条件时,如果它的左子树的右子树的高度大于它的左子树的高度:
 * 需要先对当前这个节点的左子树进行左旋转,以降低左子树的右子树的高度;
 * 然后再对当前节点进行右旋转的操作.
 * 1) 先对根节点的左子树进行左旋转,即以左子节点(7)为根节点进行左旋转操作
 *     10              10
 *  7    11    =>   8    11
 * 6 8             7 9
 *    9           6
 * 2) 然后再做右旋转
 *      10          8
 *   8    11  =>  7   10
 *  7 9          6   9  11
 * 6
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4,3,6,5,7,8}; // 需要左旋转
        // arr = new int[]{10,12,8,9,7,6}; // 需要右旋转
        // arr = new int[]{10,11,7,6,8,9}; // 需要双旋转
        // arr = new int[]{2,1,6,5,7,3}; // 需要双旋转
        arr = new int[]{1,2,3,4,5,6,7,8,9,10};
        var avlTree = new AVLTree();
        for(int i=0; i<arr.length; i++){
            avlTree.add(new Node(arr[i]));
        }
        avlTree.infixOrder();
        // System.out.println("===没有平衡处理之前===");
        System.out.println("树的高度:"+avlTree.root().height());
        System.out.println("左子树的高度:"+avlTree.root().leftHeight());
        System.out.println("右子树的高度:"+avlTree.root().rightHeight());
        System.out.println("当前根节点:"+avlTree.root());
        System.out.println("当前根节点的左子节点:"+avlTree.root().left
                +", 当前根节点的右子节点:"+avlTree.root().right);

        /*
        avlTree.root().leftRotate();
        System.out.println("=====左旋转之后=====");
        avlTree.infixOrder();
        System.out.println("树的高度:"+avlTree.root().height());
        System.out.println("左子树的高度:"+avlTree.root().leftHeight());
        System.out.println("右子树的高度:"+avlTree.root().rightHeight());
         */
    }
}

class AVLTree {
    private Node root;

    public Node root() {
        return root;
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空,不能遍历");
        }
    }

    public Node search(int value) {
        if (root == null) return null;
        return root.search(value);
    }

    public Node searchParent(int value) {
        if (root == null) return null;
        return root.searchParent(value);
    }

    public void delete(int value) {
        if (root == null) return;
        // 如果要删除的是root,且
        if (root.value == value) {
            // 如果树中只有这一个节点,则直接置空
            if (root.left == null && root.right == null) {
                root = null;
                return;
                // 如果树中左子树不为空,右子树为空,则上提左子树
            } else if (root.left != null) {
                root = root.left;
                return;
                // 如果树中右子树不为空,左子树为空,则上提右子树
            } else {
                root = root.right;
                return;
            }
        }
        Node targetNode = search(value);
        if (targetNode == null) return;
        Node parent = searchParent(value);
        // 不需要检查parent是否为空,因为此时的parent必然不为空
        // 如果要删除的节点是叶子节点
        if (targetNode.left == null && targetNode.right == null) {
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if (parent.left != null && parent.left.value == value) {
                parent.left = null;
            }
            // 要删除的是父节点的右子节点
            if (parent.right != null && parent.right.value == value) {
                parent.right = null;
            }
        }
        // 删除有两颗树的非叶子节点
        // 需要从子树中找到一个节点代替被删除节点的位置,需要满足二叉排序树的要求
        // 即替代节点的值要大于左子树,小于右子树
        // 即可以选择左子树的最大节点或者右子树的最小节点
        else if (targetNode.left != null && targetNode.right != null) {
            // 删除targetNode的右子树最小节点
            int rightMinVal = delRightTreeMin(targetNode.right);
            // 将最小节点的值赋给当前待删除节点,完成替代
            targetNode.value = rightMinVal;
        }
        // 删除只有一颗树的非叶子节点
        // 如果有左子节点
        else if (targetNode.left != null) {
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if (parent.left != null && parent.left.value == value) {
                parent.left = targetNode.left;
            }
            // 要删除的是父节点的右子节点
            if (parent.right != null && parent.right.value == value) {
                parent.right = targetNode.left;
            }
        }
        // 如果有右子节点
        else if (targetNode.right != null) {
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if (parent.left != null && parent.left.value == value) {
                parent.left = targetNode.right;
            }
            // 要删除的是父节点的右子节点
            if (parent.right != null && parent.right.value == value) {
                parent.right = targetNode.right;
            }
        }
    }

    /**
     * @param node 二叉排序树的root
     * @return 返回以node为根节点的二叉排序树的最小值的节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        // 循环查找左节点,找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // target指向最左端节点,即最小值
        delete(target.value);
        return target.value;
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }
    public int leftHeight(){
        if(left==null) return 0;
        return left.height();
    }
    public int rightHeight(){
        if(right==null) return 0;
        return right.height();
    }
    // 以该节点为根节点的树的高度
    public int height(){
        return Math.max(
                // 左子树的高度,递归的次数就是层数
                left==null?0:left.height(),
                // 右子树的高度
                right==null?0:right.height()
        // 本层的层数,帮助递归次数进行实际的计算
        )+1;
    }

    // 左旋转的方法
    public void leftRotate(){
        // 左旋转时,当前树根节点(其实就是当前节点)作为旋转中心节点,将下沉一层
        Node newNode = new Node(this.value);
        // 左旋转时,左子树不动
        newNode.left = this.left;
        // 将右子树的左子树挂到下沉节点的右侧
        newNode.right = this.right.left;
        // 下沉节点的原右子节点将上升为新的根节点,其值覆盖原根节点(即下沉节点)
        this.value = this.right.value;
        // 上升节点的右子树挂到新的根节点的右侧
        // 注意:此时,this和this.right的值一样,
        // 但this是新的根节点,this.right是飞升节点,肉身将被废弃
        this.right = this.right.right;
        // 新的根节点的左子树挂上原根节点
        this.left = newNode;
    }
    // 右旋转的方法
    public void rightRotate(){
        Node newNode = new Node(this.value);
        // 右旋转时,右子树不动
        newNode.right=this.right;
        // 左子树的右子树挂到新节点的左侧
        newNode.left=this.left.right;
        // 下沉节点(当前节点,即根节点)的左子节点将上升为新的根节点,其值覆盖当前节点的值
        this.value=this.left.value;
        // 将上升节点的左子树挂到新的根节点的左侧
        // 注意,此时,this和this.left的值一样
        // 但this是新的根节点,this.left将被断开与其它节点的连接
        this.left=this.left.left;
        // 将新节点挂到当前节点的右子树上
        this.right=newNode;
    }
    /**
     * @param value 待查找的节点的值
     * @return
     */
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            if (left == null) return null;
            return left.search(value);
        } else {
            if (right == null) return null;
            return right.search(value);
        }
    }

    public Node searchParent(int value) {
        if ((left != null && left.value == value)
                || (right != null && right.value == value)) {
            return this;
        }
        if (left != null && value < this.value) {
            return left.searchParent(value);
        } else if (right != null && value >= this.value) {
            return right.searchParent(value);
        }
        return null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    // 以递归的方式添加节点,并满足二叉排序树的要求
    public void add(Node node) {
        if (node == null) return;

        // 如果插入的新节点的值小于当前节点,则新节点向左放置
        if (node.value <= this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        int rightHeight = rightHeight();
        int leftHeight = leftHeight();
        // 当添加完一个节点后,如果右子树的高度比左子树高2及以上,就需要左旋转
        if(rightHeight-leftHeight>1){
            // 如果右子树的左子树的高度比右子树的右子树高,则需要先对右子树做一次右旋转,
            // 降低右子树的左子树的高度
            if(this.right!=null
                    && this.right.leftHeight()>this.right.rightHeight()){
                this.right.rightRotate();
            }
            leftRotate();
            // 已经平衡了,不需要再继续旋转了
            return;
        }
        // 当添加完一个节点后,如果左子树的高度比右子树高2及以上,就需要右旋转
        if(leftHeight-rightHeight>1){
            // 左子树的右子树的高度大于左子树的左子树的高度
            if (this.left!=null
                    && this.left.rightHeight() > this.left.leftHeight()){
                // 对左子树进行左旋转,降低左子树的右子树的高度
                this.left.leftRotate();
            }
            rightRotate();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}
